package 动态规划;

public class No516最长回文子序列 {

    /**
     * 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
     *
     * 示例 1:
     * 输入:
     * "bbbab"
     * 输出:
     * 4
     * 一个可能的最长回文子序列为 "bbbb"。
     *
     * 示例 2:
     * 输入:
     * "cbbd"
     * 输出:
     * 2
     * 一个可能的最长回文子序列为 "bb"。
     */

    /**
     * 本子有记录
     * 单串的dp一般都是区间[i,j]范围内符合的个数
     * 本题dp根据本子推导出
     * f(i,j)= f(i-1,j-1)+2=>if(str[i]==str[j]) || max(f(i+1,j),f(i,j-1))
     */
    public int longestPalindromeSubseq(String s) {

        int[][] dp=new int[s.length()][s.length()];

        //base [i,i]区间为1
        for (int i = 0; i < s.length(); i++) {
            dp[i][i]=1;
        }

        //横着来
        for (int j = 1; j < s.length(); j++) {
            for (int i = j-1; i >= 0; i--) {

                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }

            }
        }

        return dp[0][s.length()-1];
    }

    public static void main(String[] args) {
        No516最长回文子序列 n=new No516最长回文子序列();
        int result = n.longestPalindromeSubseq("cbxabyc");
        System.out.println(result);
    }

}